package com.kizuki.algorithm.leetcode;

/**
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * https://leetcode-cn.com/problems/first-missing-positive/
 */
public class 缺失的第一个正数{

    class Solution {
        public int firstMissingPositive(int[] nums) {
            int len = nums.length;
            for(int i = 0; i < len; i++) {
                while(nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
                    int temp = nums[i];
                    nums[i] = nums[temp - 1];
                    nums[temp - 1] = temp;
                }
            }

            for(int i = 0; i < len; i++) {
                if (i + 1 != nums[i]) {
                    return i + 1;
                }
            }
            return len + 1;
        }
    }

}
